package com.huawei.M01.iterator;

import java.util.Arrays;

/**
 * 利用前序和后序遍历结果构造原树
 *
 * @author zhiwu
 */
public class BuildTreePrePost {
    class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode() {
        }
    }

    public TreeNode constructorTreePrePost(int[] pre, int[] post) {
        int N = pre.length;
        if (N == 0) {
            return null;
        }
        // 前序遍历的第一个值便是树的根节点
        TreeNode root = new TreeNode(pre[0]);
        if (N == 1) {
            return root;
        }
        int index = 0;
        // 遍历前序和后序结果，找到左分支的根节点
        for (int i = 0; i < N; i++) {
            if (pre[1] == post[i]) {
                index = i + 1;
                break;
            }
        }
        root.left = constructorTreePrePost(
                Arrays.copyOfRange(pre, 1, index + 1),
                Arrays.copyOfRange(post, 0, index)
        );

        root.right = constructorTreePrePost(
                Arrays.copyOfRange(pre, index + 1, N),
                Arrays.copyOfRange(post, index, N - 1)
        );
        return root;
    }
}
